% Find which edge to add helps the graph the most
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% function [bestx,besty] = helpGraph(G,varargin);
%  
%   This function cycles through all possible edges to add to the graph and
%   see which helps the most
%
%   INPUTS:     G - adjacency matrix for graph G
%
%   OUTPUTS:    bestx - one vertex for best edge to add to G
%               besty - one vertex for best edge to add to G
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function [bestx,besty,minEccentricity] = helpGraph(G,varargin);

% Get sizes & initialize some values
[xmax ymax] = size(G);
bestx = 0;
besty = 0;
% Get initial values
distances = GetDistances(G);
[eccentricities, graphDiameter, graphRadius, ... 
    graphCenters, graphExtremes] = GetEccentricities(distances);
avgEccentricity = sum(eccentricities)/xmax;
minEccentricity = avgEccentricity


for x = 1:xmax
    for y = x:ymax
        % test the new edge for average eccentricity
        Gtest = addEdge(x,y,G);
        distances = GetDistances(Gtest);
        [eccentricities, graphDiameter, graphRadius, ... 
            graphCenters, graphExtremes] = GetEccentricities(distances);
        avgEccentricity = sum(eccentricities)/xmax;
        % if new edge causes a lower than minimum eccentricity, record it
        if (avgEccentricity < minEccentricity),
            minEccentricity = avgEccentricity;
            bestx = x;
            besty = y;
        end;
    end;
end;